"""
题目：实现一个函数，在双链表的末尾插入一个新节点。
"""


class Node:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next


def insert_at_end(head, val):
    new_node = Node(val)  # 创建新节点

    # 特殊情况：链表为空，新节点成为头节点
    if not head:
        return new_node

    # 遍历到尾节点
    current = head
    while current.next:  # 当current.next不为空时继续移动
        current = current.next

    # 插入新节点
    current.next = new_node  # 尾节点的next指向新节点
    new_node.prev = current  # 新节点的prev指向尾节点

    return head  # 头节点不变，返回原头节点


# 辅助函数（复用）
def create_doubly_linked_list(arr):
    if not arr:
        return None
    head = Node(arr[0])
    current = head
    for val in arr[1:]:
        new_node = Node(val)
        current.next = new_node
        new_node.prev = current
        current = new_node
    return head


def traverse_forward(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result


# 测试
head = create_doubly_linked_list([1, 2, 3])
head = insert_at_end(head, 4)  # 在末尾插入4
head = insert_at_end(head, 5)  # 在末尾插入5
print(traverse_forward(head))  # 输出: [1, 2, 3, 4, 5]
